package real.jd.string;

import org.junit.Test;

public class MinAddChars {
    //添加最少字符使得s + str包含两个s
    public String addMinChars(String s) {
        int next[] = getNext(s);
        int len = s.length();
        return s.substring(next[len]);
    }

    public int[] getNext(String s) {
        int len = s.length(), last = 0, i = 2;
        int[] next = new int[len + 1];
        next[0] = -1;
        next[1] = 0;
        while (i <= len) {
            if (s.charAt(i - 1) == s.charAt(last)) {
                next[i++] = ++last;
            } else if (last > 0) {
                last = next[last];
            } else {
                next[i++] = 0;
            }
        }
        return next;
    }

    @Test
    public void test() {
        System.out.println(addMinChars("aaaaaa"));
    }
}
